/**
 * This is an implementation of a map structure where the keys are stored
 * in a binary search tree.  Because of this, we add the constraint that
 * the keys must be of type Comparable so that we can enforce an ordering.
 * 
 * @param <K> the type of the keys (must be Comparable)
 * @param <V> the type of the values
 */

import java.util.Set;
import java.util.TreeSet;

public class MyTreeMap<K extends Comparable<K>, V> implements MyMap<K, V>
{
	
	// The root node of the binary search tree
	public TreeMapNode<K, V> root;
	
	
	private TreeMapNode<K, V> preNode;
	
	public MyTreeMap()
	{
		this.clear();
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 * insert -- will recursively insert a node into the BST
	 * @param node -- the node need to be insert
	 * @param curr -- pointer to the current position
	 */
	private void insert(TreeMapNode<K, V> node, TreeMapNode<K, V> curr){
		
		// compare new node and current node
		int result = node.getKey().compareTo(curr.getKey());
		// new node < current node
		if (result < 0 ){
			// left side of current node is empty
			if (curr.getLeft() == null){
				curr.setLeft(node);
				return;
			}
			
			// compare new node and left side node
			result = node.getKey().compareTo(curr.getLeft().getKey());
			
			// left side < new node
			if (result < 0){
				// recursive to insert the node
				insert(node,curr.getLeft());
				return;
			}
			// left side > new node
			else if (result > 0){
				// left side has no right child, just insert it
				if (curr.getLeft().getRight() == null){
					curr.getLeft().setRight(node);
					return;
				}
				// recursive to insert the node
				insert(node, curr.getLeft().getRight());
				return;
			}
			else{
				System.out.println("got 2 node equation 1");
				return;
			}
				
			
		}
		else if (result > 0){
			// right side of current node is empty
			if (curr.getRight() == null){
				curr.setRight(node);
				return;
			}
			
			result = node.getKey().compareTo(curr.getRight().getKey());
			// new node > right side
			if (result > 0){
				//recursive insert the node 
				insert(node,curr.getRight());
				return;
			}
			// new node < right side
			else if (result < 0){
				// right side does not have left child, just insert it
				if (curr.getRight().getLeft() == null){
					curr.getRight().setLeft(node);
					return;
				}
				//recursive insert the node
				insert(node,curr.getRight().getLeft());
				return;
			}
			else{
				System.out.println("got 2 node equation 2");
				return;
			}
		}
		else{
			System.out.println("got 2 node equation 3");
			return;
		}
		
	}
	
	/**
	 * findNode -- will find out whether a specific key is in the BST
	 * @param key -- the specific key
	 * @param curr -- current node
	 * @return -- return null if the key is not found otherwise the node which has that keys
	 */
	private TreeMapNode<K, V> findNode(K key, TreeMapNode<K, V> curr){
		// check the input validation
		if (curr == null){
			return null;
		}
		
		// compare the specified node and current node
		int result = key.compareTo(curr.getKey());
		
		// found the node
		if (result == 0){
			return curr;
		}
		// specified node > curr node
		else if (result > 0){
			// to the end of the tree
			if (curr.getRight() == null){
				return null;
			}
			
			//recursively search
			this.preNode = curr;
			return findNode(key, curr.getRight());
		}
		else if (result < 0){
			// to the end of the tree
			if (curr.getLeft() == null){
				return null;
			}
			
			// recursively search
			this.preNode = curr;
			return findNode(key, curr.getLeft());
		}
		else{
			System.out.println("Error in findNode");
			return null;
		}
	}
	public void put(K key, V val)
	{
		// can not insert same key
		if (this.contains(key)){
			return;
		}
		TreeMapNode<K, V> node = new TreeMapNode<K, V>(key,val);
		node.setLeft(null);
		node.setRight(null);
		
		// for the empty tree
		if (root == null){
			root = node;
			return;
		}
		
		this.insert(node, root);
		return;
		// same key will not exist in map, the new value with the same key will
		// rewrite the old one
		
		
		//throw new RuntimeException("You must implement this method!");
	}
	
	
	/**
	 * traverse -- will traverse all the BST to extract the key
	 * @param set -- the set need to fill key
	 * @param node -- current node
	 * @return return set contains keys
	 */
	private Set<K> traverse(Set<K> set, TreeMapNode<K, V> node){
		// check the node
		if (node == null){
			return set;
		}
		
		set.add(node.getKey());
		// check the children
		// check the left
		if (node.getLeft() == null){
			;
		}
		else{
			set = traverse(set, node.getLeft());
		}
		
		// check right
		if (node.getRight() == null){
			return set;
		}
		else{
			return traverse(set, node.getRight());
		}
	}
	
	
	/**
	 * findMin -- will find out the min node in the BST
	 * @param node -- head node of the BST
	 * @return -- return the min node, return null if the head node is null
	 */
	public TreeMapNode<K, V> findMin(TreeMapNode<K, V> node){
		// check the input
		if (node == null){
			return null;
		}
		
		// check left side
		if (node.getLeft() == null){
			return node;
		}
		else{
			this.preNode = node;
			return findMin(node.getLeft());
		}
	}
	
	private void redirectNode(TreeMapNode<K, V> parent, K key, TreeMapNode<K, V> replace){
		// for the root 
		if (parent == null){
			root = replace;
			return;
		}
		
		// previous node's left side points to desired node
		if (parent.getLeft() != null){
			if (parent.getLeft().getKey().equals(key)){
				parent.setLeft(replace);
				return;
			}
		}	
		
		if (parent.getRight() != null){
			if (parent.getRight().getKey().equals(key)){
				parent.setRight(replace);
				return;
			}
		}
		System.out.println("Error at redirectNode");
	}
	
	public V get(K key)
	{
		TreeMapNode<K,V> node = findNode(key, root);
		if (node == null){
			System.out.println("cannot find the the key");
			return null;
		}
		
		return node.getValue();
		
		//throw new RuntimeException("You must implement this method!");
	}
	
	public boolean remove(K key)
	{
		// check whether the key is exist
		if (!this.contains(key)){
			System.out.println("specific key is not found");
			return false;
		}
		
		
		// combo operation for findNode
		this.preNode = null;
		TreeMapNode<K, V> node = this.findNode(key, root);
		TreeMapNode<K, V> tmp = this.preNode;
		if (node == null){
			System.out.println("result is null");
		}
		// if the key is leaf with no children
		if (node.getLeft() == null && node.getRight() == null){
			this.redirectNode(tmp, key, null);
			return true;
		}
		// the key has only one child
		else if (node.getLeft() == null){
			this.redirectNode(tmp, key, node.getRight());
			return true;
		}
		else if (node.getRight() == null){
			this.redirectNode(tmp, key, node.getLeft());
			return true;
		}
		// the key has two children
		else{
			// save the parent node
			TreeMapNode<K, V> parent = tmp;
			
			// find out min node in the right subtree of the node which need to be removed
			this.preNode = null;
			// the min must exist because the previous process already handle none 
			// exist situation
			TreeMapNode<K, V> min = this.findMin(node.getRight());
			// remove min node from the BST(min should be a leaf node, easy to delete)
			this.remove(min.getKey());
			// use the min node to replace the removed node
			min.setLeft(node.getLeft());
			min.setRight(node.getRight());
			this.redirectNode(parent, key, min);
			return true;
		}
		//throw new RuntimeException("You must implement this method!");
	}
	
	public boolean contains(K key)
	{
		if (findNode(key,root) == null){
			return false;
		}
		else{
			return true;
		}
		//throw new RuntimeException("You must implement this method!");
	}
	
	public void clear()
	{
		root = null;
		preNode = null;
		//throw new RuntimeException("You must implement this method!");
	}
	
	public Set<K> keySet()
	{
		Set<K> set = new TreeSet<K>();
		return traverse(set, root);	
		//throw new RuntimeException("You must implement this method!");
	}
	
	public void traversePrint(TreeMapNode<K, V> node, int count, StringBuffer sb){
		// check the node
		if ( node == null){
			return;
		}
		int cnt = count*10;
		sb.append("[" + count + ":" + node.getValue() + "],");
		
		if (node.getLeft() == null){
			sb.append("[" + (cnt-1) + ":],");
		}
		else{
			traversePrint(node.getLeft(), cnt-1, sb);
		}
		
		if (node.getRight() == null){
			sb.append("[" + (cnt+1) + ":],");
		}
		else{
			traversePrint(node.getRight(), cnt+1, sb);
		}
		
		return;
		
	}
	public String toString(){
		StringBuffer sb = new StringBuffer();
		int count = 1;
		traversePrint(root, count, sb);
		return sb.toString();
	}
}
